﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0045_OrangesRotting : IAlgorithm
    {
        // 994. 腐烂的橘子

        // 在给定的网格中，每个单元格可以有以下三个值之一：
        //  值 0 代表空单元格；
        //  值 1 代表新鲜橘子；
        //  值 2 代表腐烂的橘子。
        // 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。

        // 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。

        // 提示：
        //  1 <= grid.length <= 10
        //  1 <= grid[0].length <= 10
        //  grid[i][j] 仅为 0、1 或 2

        public void Test()
        {
            // 算法参数定义
            var grid = new int[][] {
                new int[]{ 2,1,1 },
                new int[]{ 1,1,0 },
                new int[]{ 0,1,1 },
            };
            // 算法执行与打印
            Console.WriteLine(OrangesRotting(grid));
        }

        // 算法
        // 以2为起点
        public int OrangesRotting(int[][] grid)
        {
            var queue = new Queue<int[]>();
            for (int i = 0; i < grid.Length; i++)
                for (int j = 0; j < grid[0].Length; j++)
                    if (grid[i][j] == 2)
                    {
                        queue.Enqueue(new int[] { i, j });
                        grid[i][j] = 0;
                    }
                    else if (grid[i][j] == 1)
                    {
                        grid[i][j] = -1;
                    }
            int[] directions = { -1, 0, 1, 0, -1 };
            int step = 1;
            while (queue.Count > 0)
            {
                int size = queue.Count;
                for (int i = 0; i < size; i++)
                {
                    var tempPoint = queue.Dequeue();
                    for (int j = 0; j < directions.Length - 1; j++)
                    {
                        int x = tempPoint[0] + directions[j];
                        int y = tempPoint[1] + directions[j + 1];
                        if (x < 0 || x == grid.Length || y < 0 || y == grid[0].Length || grid[x][y] >= 0)
                            continue;
                        queue.Enqueue(new int[] { x, y });
                        grid[x][y] = step;
                    }
                }
                step++;
            }
            int result = 0;
            for (int i = 0; i < grid.Length; i++)
                for (int j = 0; j < grid[0].Length; j++)
                    if (grid[i][j] == -1)
                        return -1;
                    else
                        result = Math.Max(result, grid[i][j]);
            return result;
        }
    }
}
